A variety of public key cryptography protocols are known for encoding information, authenticating entities to one another, and electronically signing messages. Examples of such protocols include RSA, El Gamal, Schnorr and Fiat Schamir. A common feature of public key cryptography protocols is the fact that they employ large prime numbers, with typical lengths in the range of 512–2048 bits, to form one or more keys of the protocol. Some of these cryptosystems, such as RSA for example, require the random generation of several distinct prime numbers. Thus, generating prime numbers is an essential tool in public key cryptography.
When efficiency is not a concern, one of the simplest ways to generate a random prime number is to select a random number q and test it for primality. If the test is unsuccessful, the value for q is incremented by one, and the test is rerun. Since all prime numbers except two are odd, a straightforward improvement on this technique is to choose q as an odd value, and to update it in increments of two for each successive iteration of the test. However, this technique can become computationally intensive and is therefore not practical in a number of situations when large-sized numbers are employed.
To facilitate the random number selection process, several techniques have been developed that make it possible to more efficiently calculate the greatest common denominator of two numbers, and thereby determine whether they are co-prime. Examples of those techniques include Binary GCD, Extended GCD and the Lehmer formula. While these techniques exhibit excellent asymptotic complexity for numbers of extremely large size, they are difficult to program in an environment having limited processing resources, such as a smart card or other portable electronic device. In addition, they provide relatively poor performance for operations involving numbers of the size typically employed in the smart card environment, e.g. in the range of 512 to 1024 bits. To increase the performance, it is possible to equip the card with an arithmetic coprocessor to carry out some of the operations of the primality test. However, other operations that are performed as part of the test, such as parity checking and binary shifts, are not compatible with the functionality typically offered in an arithmetic coprocessor. As a result, the overall performance still suffers.
To address these issues, one technique for generating a random prime number is disclosed in published PCT Application WO 02/05483, the contents of which are incorporated herein by reference. This application discloses a method for generating an electronic key from a prime number q contained in a specific interval of positive integers [qmin, qmax]. In this method, a positive integer x is chosen with x being the product of k prime numbers, where k is a maximum so that there exist two positive integers εm and εM, such that εm is the higher roundoff of qmin/x, and εM is the lower roundoff of (qmax−qmin)/x. The values π=εM·x and ρ=εm·x are calculated, and two positive integers a and c belonging to the multiplicative group Zπ* of integers (modulo π) are selected. Once these precalculations have been made, a candidate value q=c+ρ is calculated, and the primality of q is tested. If q is a prime number, it is returned, or stored, as the random prime number of interest. Otherwise, c is updated by calculating ac (modulo π) and repeating the preceding operation with the new value q=c+ρ.
A limitation associated with this approach can arise from the fact that the precalculated data approximates the interval [qmin, qmax] only when the value for ρ is close to qmin and the value for ρ+π is close to qmax. The values for π and ρ are therefore a function of the desired interval. A different interval requires a different set of precalculated values. The need to store all of these values may be undesirable in an environment having limited storage capacity, such as a portable electronic device.
It is an objective of the present invention to reduce the number of precalculated values, and thereby achieve an economy of storage. It is a further objective to provide a finer approximation of the interval [qmin, qmax] of interest, while utilizing a value for π that can be applied over a number of different intervals.